home *** CD-ROM | disk | FTP | other *** search
/* This file demonstrates how ApplicationIdle can be used to drive, a complicated computation in an application written from MacStarter. To use this file, you should add it to the MacStarter.π project and delete the current applicationProcs file. The problem in this case is the solution of "pentomino puzzles." A pentomino is a tile consisting of 5 connected squares. There are exactly 12 different possilbe pentominos. The puzzles involve placing one of each type of pentomino on an 8-by-8 board. This will leave four blank spaces. In this program, the spaces that are to be left blank are specified in advance. The basic algorithm used is a simple recursive depth-first search: Try to place a piece at the first empty square; if it fits, go on to the next empty space and repeat; if the puzzle isn't solved fails, try the next piece; if there is no other piece to try, then there is no solution. Unfortunately, I can't really use a single recursive function because I am insisting that each call to ApplicationIdle only do a part of the problem. There is also an interesting problem of data representation, which is commented on below even though it has nothing to do with MacStarter. This program can be set to continue running in the background under system 7 or multifinder. Before building the application, go to the Set Project Type command in the Project menu. There is a small icon labeled "SIZE flags". This will turn into a pop-up menu if you click on it. Simply choose the command "Background Null Events" from this menu. Then, ApplicationIdle will continue to be called even when the application is in the background. All places where this file has been modified (from the original applicationProcs.c) are commented with comments that begin with // */ #include "globals-MacStarter.h" long gEventWaitTime = 0; // Changed from 100000 to 0 so that the // function ApplicationIdle will be called // as often as possible. MenuHandle editMenu, fileMenu; void InitApplication(void); void UpdateMenus(void); void DoEditMenu(int itemNum); void DoFileMenu(int itemNum, int* done); void DoOtherMenu(int menuID, int itemNum); void ApplicationIdle(void); void CleanUpApplication(void); void AboutBox(void); void DoNewCommand(void); const short squareSize = 21; // This is the size of each square in the // 8-by-8 playing board. It can be // adjusted slightly to make larger or // smaller boards. short WindowCt = 0; // This variable will count the number of windows // that have been opened so far. It is incremented // in DoNewCommand and is used in OpenInRect to // position the window. typedef short boardData[100]; // The 8-by-8 board is actually // represented by a 10-by-10 data structure // in which the cells along the border // are declared permanently "filled" // This simplifies testing whether a given // piece fits at a given position on the // board. Furthermore, this 10-by-10 board // is represented by a 1-dimensional array // in which the 10*i+j-th entry represents // row j and column i on the board. const pieces[63][5] = { { 1, 1,2,3,4 }, // This array represents everything the program { 1, 10,20,30,40 }, // knows about the individual pentominos. Each { 2, 9,10,11,20 }, // row in the array represents a particular { 3, 1,10,19,20 }, // pentomino in a particular orientation. Different { 3, 10,11,12,22 }, // orientations are obtained by rotating or flipping { 3, 1,11,21,22 }, // the pentomino over. Note that the program must { 3, 8,9,10,18 }, // try each pentomino in each possible orientation, { 4, 10,20,21,22 }, // but must be careful not to reuse a piece if { 4, 1,2,10,20 }, // it has already been used on the board in a { 4, 10,18,19,20 }, // different orientation. { 4, 1,2,12,22 }, // The pentominoes are numbered from 1 to 12. { 5, 1,2,11,21 }, // The first number on each row tells which pentomino { 5, 8,9,10,20 }, // that row represents. Note that there can be { 5, 10,19,20,21 }, // up to 8 different rows for each pentomino. { 5, 10,11,12,20 }, // some pentominos have fewer rows because they are { 6, 10,11,21,22 }, // symmetric. For example, the pentomino that looks { 6, 9,10,18,19 }, // like: { 6, 1,11,12,22 }, // GGG { 6, 1,9,10,19 }, // G G { 7, 1,2,10,12 }, // { 7, 1,11,20,21 }, // can be rotated into three additional positions, { 7, 2,10,11,12 }, // but flipping it over will give nothing new. { 7, 1,10,20,21 }, // So, it has only 4 entries in the array. { 8, 10,11,12,13 }, // The four remaining entries in the array { 8, 10,20,29,30 }, // describe the given piece in the given orientation, { 8, 1,2,3,13 }, // in a way convenient for placing the piece into { 8, 1,10,20,30 }, // the one-dimensional array that represents the { 8, 1,11,21,31 }, // board. As an example, consider the row { 8, 1,2,3,10 }, // { 8, 10,20,30,31 }, // { 7, 1,2,10,19 } { 8, 7,8,9,10 }, // { 9, 1,8,9,10 }, // If this piece is placed on the board so that { 9, 10,11,21,31 }, // its topmost/leftmost square fills position { 9, 1,2,9,10 }, // p in the array, then the other four squares { 9, 10,20,21,31 }, // will be at positions p+1, p+2, p+10, and p+19. { 9, 1,11,12,13 }, // To see whether the piece can be played at that { 9, 10,19,20,29 }, // position, it suffices to check whether any of { 9, 1,2,12,13 }, // these five squares are filled. If the piece is { 9, 9,10,19,29 }, // played, those five places in the array are filled { 10, 8,9,10,11 }, // with a letter representing the pentomino ('A' for { 10, 9,10,20,30 }, // pentomino 1, 'B' for pentomino 2, etc.) { 10, 1,2,3,11 }, { 10, 10,20,21,30 }, { 10, 1,2,3,12 }, { 10, 10,11,20,30 }, { 10, 9,10,11,12 }, { 10, 10,19,20,30 }, { 11, 9,10,11,21 }, { 11, 1,9,10,20 }, { 11, 10,11,12,21 }, { 11, 10,11,19,20 }, { 11, 8,9,10,19}, { 11, 1,11,12,21 }, { 11, 9,10,11,19 }, { 11, 9,10,20,21 }, { 12, 1,10,11,21 }, { 12, 1,2,10,11 }, { 12, 10,11,20,21 }, { 12, 1,9,10,11 }, { 12, 1,10,11,12 }, { 12, 9,10,19,20 }, { 12, 1,2,11,12 }, { 12, 1,10,11,20 }, }; typedef enum { // This type is a convenienct for keeping track a board's status. settingUp, // = The user has not yet chosen the four empty spaces. running, // = The program is looking for a solution. finished, // = A solution has been found and is being displayed noSolution // = After trying all possibilities, no solution has been found } winState; // Declare two functions for placing pieces and removing pieces from the // board. Note that these functions are responsible for maintaining both // the screen and the board data structure. (It is not a good idea to // separate such functions.) These are both called by the higher level // function myWindow::playPiece. short putPiece(short piece, short where, boardData board); short erasePiece(short piece, short where, boardData board); // Function putPiece tries to place a specifed piece in a specified position // on the board boardData. If all the locations needed by the piece are // empty, then this function fills in those spaces in the array with the // number of the pentomino and also draws the piece on the board. // In this case, a value of 1 is returned. If the piece cannot be played, // a value of 0 is returned. This function assumes that the drawing port is // set to the correct window. Note that the parameter pieceNum is an index // to the data for the piece in the global array "pieces"; the actual number of // the pentomino being played is thus pieces[pieceNum][0]. short putPiece(short pieceNum, short where, boardData board){ short i,j,k,loc; // test if any of the spaces are already filled if (board[where]) return 0; for (i=1; i<5; i++) if (board[ where + pieces[pieceNum][i] ]) return 0; // if the piece can be played, then do so. board[where] = pieces[pieceNum][0] - 1 + 'A'; k = where % 10; j = where / 10; MoveTo((k-1)*squareSize+8,(j-1)*squareSize+14); DrawChar(board[where]); for (i=1; i<5; i++) { loc = where + pieces[pieceNum][i]; board[loc] = pieces[pieceNum][0]-1+'A'; k = loc % 10; j = loc / 10; MoveTo((k-1)*squareSize+8,(j-1)*squareSize+14); DrawChar(board[loc]); if (board[loc] == '@') { k++; } } return 1; } // Function erasePiece is called to remove a piece from the board // and from the screen. It is assumed that the drawing port is set // to the appropriate window when the function is called. // It is also assumed that the specified piece is actually at the // specified location!! short erasePiece(short pieceNum, short where, boardData board){ short i,j,k,loc; k = where % 10; j = where / 10; MoveTo((k-1)*squareSize+8,(j-1)*squareSize+14); DrawChar(board[where]); board[where] = 0; for (i=1; i<5; i++) { loc = where + pieces[pieceNum][i]; k = loc % 10; j = loc / 10; MoveTo((k-1)*squareSize+8,(j-1)*squareSize+14); DrawChar(board[loc]); board[loc] = 0; }; return 1; } class myWindow : public xWindow { // Data needed for this window; each window represents one puzzle board winState state; // window state; type winState is defined above boardData filled; // data for the puzzle board associated with this window short clicked; // how many squares has the user clicked on? These are // the squares that are to remain empty. When the // user has clicked on four such squares, the program // starts solving the puzzle. short played; // how many pieces are currently played on the board? short used[13]; // used[p] is set to 1 if pentomino number p is currently // on the board (used[0] is not used) short pieceStack[12]; // pieceStack[0],...,pieceStack[played-1] give the // list of pieces currently on the board. Each entry // is actually an index to the global array "pieces". // It is possible that pieces[played-1] is -1, // indicating that no piece has yet been tried on // the current top "level of recursion". short squareStack[13];// squareStack[0],...,squareStact[played-1] record the // next empty square on the board after each // of the pieces in pieceStack was played public: void playPiece(void); // this is a new function, responsible for placing // the next piece on the board. virtual void OpenInRect(Str255 title, int left, int top, int right, int bottom); virtual short Close(void); protected: virtual void SetDefaults(void); virtual void doKey(char ch); virtual void doContentClick(Point localPt); virtual void adjustToNewSize(void); virtual void doRedraw(Rect* badRect); virtual void doHScroll(int dh); virtual void doVScroll(int dv); virtual void doActivate(int active); }; // Function playPiece is called by function ApplicationIdle to place the // next piece on the board. It does just one step in solving the puzzle. // Actually, this function is called only for the first window in the // list of windows, xWindowList, which contains all the windows currently // open in the program. (xWindowList is a global variable.) The function // call is passed down this list by the first statement of this function, // so that each window gets a chance to do one step in its puzzle. // (This is the heart of the algorithm that solves the pentominos puzzle. // It imitates a recursive, depth-first search.) void myWindow::playPiece(void) { short pieceNum; short emptySquare; if (nextWindow) // pass function call down chain of open windows. ((myWindow*)nextWindow)->playPiece(); if (state != running) // this function doesn't do anything return; // in a window that isn't currently "running" SetPort(theWindow); do { // Imagine here that you are on one level of the recursion, // and you have just returned from trying all the possibilities // at other levels. You want to try the next possible piece // on this level. That is what is done by this body of this // do loop, except that it also handles the two extreme cases: // when you first get to this level (indicated by a value of -1 // in pieceStack[played]) and when there are no other pieces to // play (indicated when pieceNum becomes 63, which causes you // to back up one level and repeat the do loop on that level); // If you back up all the way to the top level, then you know // there are no solutions). emptySquare = squareStack[played]; if (pieceStack[played] > -1) { // remove previous piece tried, if any ForeColor(whiteColor); erasePiece(pieceStack[played],squareStack[played],filled); ForeColor(blackColor); used[pieces[pieceStack[played]][0]] = 0; }; for (pieceNum = pieceStack[played]+1; pieceNum < 63 && (used[pieces[pieceNum][0]] || !putPiece(pieceNum,emptySquare,filled)); pieceNum ++); // increment pieceNum until you get to a piece // that fits, or run out of pieces if (pieceNum >= 63) { // if you ran out of pieces, back up a level played--; if (played == -1) { state = noSolution; SetTitle("\pNo Solution"); SysBeep(2); return; } } } while (pieceNum >= 63); // repeat if didn't play a piece on this level pieceStack[played] = pieceNum; // record the piece that was played used[pieces[pieceNum][0]] = 1; if (played == 11) { // a solution was found SysBeep(1); SysBeep(1); SysBeep(1); SetTitle("\pClick for More"); state = finished; } else { // This really sets up a simulated call to the recursive // algorithm on the next level down played++; // advance to next level pieceStack[played] = -1; // on the new level, no piece has been tried while (filled[emptySquare]) emptySquare++; // find out which is the next square to be filled squareStack[played] = emptySquare; } } void myWindow::SetDefaults(void) { short i,j; inherited::SetDefaults(); features = hasGoAway; // The window is fixed-size with no scroll bars. clicked = 0; // Initialize window data... state = settingUp; squareStack[0] = 11; // first square on board (not counting border) played = 0; // no pieces played pieceStack[0] = -1; // indicates that no pieces have been tried yet either for (i=0; i<100; i++) // fill in the border with -1's filled[i] = -1; for (i=1; i<9; i++) // fill in the rest of the board with empty spaces (0's) for (j=1; j<9; j++) filled[j*10+i] = 0; for (i=1;i<13;i++) // for each pentomino, record that it has not been used used[i] = 0; } // Function OpenInRect has been modified to ignore the parameters that give // the window position and to use a formula of my own to set up the // window location. The windows are all the same size and each successive // windows is offset from the previous window. WindowCt is a global // variable that tells how many windows have been opened so far. void myWindow::OpenInRect(Str255 title, int left, int top, int right, int bottom) { inherited::OpenInRect(title, 40+10*(WindowCt%25), 55+10*(WindowCt%10), 40+8*squareSize-1+10*(WindowCt%25), 55+8*squareSize-1+10*(WindowCt%10)); } short myWindow::Close(void) { inherited::Close(); } // Here is a feature that is undocumented elsewhere: If the user hits any // key before clicking on four squares, the program will start solving the // puzzle; there will be some extra empty squares on the board after all 12 // pentominos have been placed. void myWindow::doKey(char ch) { if (state >= running) return; state = running; while (filled[squareStack[0]]) squareStack[0]++; SetTitle("\pPentominos"); clicked = 4; } void myWindow::doContentClick(Point localPt) { short i,j; Rect R; if (state == finished) { // After a solution has been found, the user state = running; // can restart the search for another solution SetTitle("\pPentominos");// by clicking on the window. (Note that the return; // title of the window depends on the current state.) }; if (state == settingUp) { // find which square the user clicked on, and // toggle its state (full to empty to empty to full) j = localPt.h / squareSize + 1; i = localPt.v / squareSize + 1; SetRect(&R,(j-1)*squareSize,(i-1)*squareSize,j*squareSize-1,i*squareSize-1); InvertRect(&R); filled[i*10+j] = 1 - filled[i*10+j]; if (filled[i*10+j]) clicked++; else clicked--; if (clicked == 4) { // The fourth space has just been specified; start running SetTitle("\pPentominos"); state = running; while (filled[squareStack[0]]) squareStack[0]++; // (squareStack[0] is supposed to be the first // available square; the user might have eliminated // one or more squares at the beginning of the // board.) } } } // Function doRedraw simply redraws the board as it currently exists. void myWindow::doRedraw(Rect* badRect){ Rect R; short i,j; for (i=1;i<8;i++) { // draw vertical lines MoveTo(i*squareSize-1,0); Line(0,8*squareSize); }; for (j=1;j<8;j++) { // draw horizontal lines MoveTo(0,j*squareSize-1); Line(8*squareSize,0); }; for (i=1;i<9;i++) for (j=1;j<9;j++) { // fill in squares as appropriate if (filled[j*10+i] == 1) { SetRect(&R,(i-1)*squareSize,(j-1)*squareSize,i*squareSize-1,j*squareSize-1); PaintRect(&R); } else if (filled[j*10+i]) { MoveTo((i-1)*squareSize+8,(j-1)*squareSize+14); DrawChar(filled[j*10+i]); } } } void myWindow::adjustToNewSize(void) { inherited::adjustToNewSize(); } void myWindow::doHScroll(int dh) { inherited::doHScroll(dh); } void myWindow::doVScroll(int dv) { inherited::doVScroll(dv); } void myWindow::doActivate(int active) { inherited::doActivate(active); } void InitApplication(void) { MenuHandle appleMenu; fileMenu = GetMHandle(2); editMenu = GetMHandle(3); appleMenu = GetMHandle(1); SetItem(appleMenu,1,"\pAbout Pentominos..."); // Set the program name // for first line of Apple menu DoNewCommand(); } void UpdateMenus(void) { short i; WindowPtr win; xWindow *xwin; win = FrontWindow(); if ( win && ((WindowPeek)win)->windowKind < 0 ) { EnableItem(editMenu,1); for (i=3; i<7; i++) EnableItem(editMenu,i); } else { DisableItem(editMenu,1); for (i=3; i<7; i++) DisableItem(editMenu,i); } if (win && xWindow::Window2XWindow(win,&xwin)) { EnableItem(fileMenu,2); } else { DisableItem(fileMenu,2); } } void DoEditMenu(int itemNum) { } void DoFileMenu(int itemNum, int* done) { xWindow *win; if (itemNum == 4) *done = 1; else if (itemNum == 1) DoNewCommand(); else if (itemNum == 2 && xWindow::Window2XWindow(FrontWindow(),&win)) win->Close(); } void DoOtherMenu(int menuID, int itemNum) { } // ApplicaitonIdle sends the message playPiece to the first window on the // list of open windows. (That window will in turn send the message on // down the list, so that each window will have a chance to play one // piece, each time ApplicationIdle is called.) void ApplicationIdle(void) { if (xWindowList) // check if the list is empty. ((myWindow*)xWindowList)->playPiece(); // The type cast is necessary since xWindowList is declared to be of type // xWindow, not myWindow, and only myWindows have a function playPiece. } void CleanUpApplication(void) { } // Set up information about program for the About box: void AboutBox(void) { ParamText( "\pPentominos: An entertainment", "\pDavid Eck", "\pHobart and William Smith Colleges\rGeneva, NY 14456\rE-mail: eck@hws.bitnet", "\pThis program tries to place the 12 pentominos (tiles that can be made with 5 squares) on an 8-by-8 board. Each tile is displayed with a different letter."); Alert(128,0L); } void DoNewCommand(void) { myWindow *pentWin; WindowCt++; // count the windows that have been opened/ pentWin = new myWindow; pentWin->Open("\pClick 4 Squares"); // initial title for window tells the // user what to do. } 
